Paper 2018/167
On the Existence of Three Round Zero-Knowledge Proofs
Nils Fleischhacker, Vipul Goyal, and Abhishek Jain
Abstract
We study the round complexity of zero-knowledge (ZK) proof systems. While five round ZK proofs for NP are known from standard assumptions [Goldreich-Kahan, J. Cryptology'96], Katz [TCC'08] proved that four rounds are insufficient for this task w.r.t. black-box simulation. In this work, we study the feasibility of ZK proofs using non-black-box simulation. Our main result is that three round private-coin ZK proofs for NP do not exist (even w.r.t. non-black-box simulation), under certain assumptions on program obfuscation. Our approach builds upon the recent work of Kalai et al. [Crypto'17] who ruled out constant round public-coin ZK proofs under the same assumptions as ours.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published by the IACR in EUROCRYPT 2018
- Keywords
- zero-knowledgeround complexitylower bound
- Contact author(s)
-
mail @ nilsfleischhacker de
abhishek @ cs jhu edu
goyal @ cs cmu edu - History
- 2018-02-11: received
- Short URL
- https://ia.cr/2018/167
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/167,
author = {Nils Fleischhacker and Vipul Goyal and Abhishek Jain},
title = {On the Existence of Three Round Zero-Knowledge Proofs},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/167},
year = {2018},
url = {https://eprint.iacr.org/2018/167}
}
